package leetcode.editor.cn;

//[10]正则表达式匹配
public class RegularExpressionMatching10 {
    public static void main(String[] args) {
        Solution solution = new RegularExpressionMatching10().new Solution();
        solution.isMatch("aa","a");

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //1.1 * 通配符匹配 0 次或多次
            //将j加 2，i不变  0 次
            //将i加 1，j不变  多次
        //1.2 无* 常规匹配 1 次

        //https://mp.weixin.qq.com/s/rnaFK05IcFWvNN1ppNf2ug
        public boolean isMatchWx(String s, String p) {
//            if (p == null || p.length() == 0) return (s == null || s.length() == 0);
//
//            int strLen = s.length();
//            int pLen = p.length();
//            // 最终：
//            // j == p.size()时，按照dp函数的定义，这意味着模式串p已经被匹配完了
//            // 如果s也恰好被匹配完，则说明匹配成功：
//            //
//            // i == s.size()时,检查一下p是否也匹配完
//            // 如果能匹配空串，一定是字符和 * 成对儿出现
//            // 检查是否为 x*y*z* 这种形式
//            if (s[i] == p[j] || p[j] == '.') {
//                // 匹配
//                if (j < p.size() - 1 && p[j + 1] == '*') {
//                    // 有 * 通配符，可以匹配 0 次或多次
//                    res = dp(s, i, p, j + 2)
//                            || dp(s, i + 1, p, j);
//                } else {
//                    // 无 * 通配符，老老实实匹配 1 次
//                    i++; j++;
//                    res = dp(s, i + 1, p, j + 1);
//                }
//            } else {
//                // 不匹配
//                if (j < p.size() - 1 && p[j + 1] == '*') {
//                    // 有 * 通配符，只能匹配 0 次
//                    res = dp(s, i, p, j + 2);
//                } else {
//                    // 无 * 通配符，匹配无法进行下去了
//                    return false;
//                }
//            }
//
//            // 将当前结果记入备忘录
//            memo[key] = res;
//            return res;
//
//            if (i == s.size()) {
//                // 如果能匹配空串，一定是字符和 * 成对儿出现
//                if ((n - j) % 2 == 1) {
//                    return false;
//                }
//                // 检查是否为 x*y*z* 这种形式
//                for (; j + 1 < p.size(); j += 2) {
//                    if (p[j + 1] != '*') {
//                        return false;
//                    }
//                }
//
//
//            }


            return true;
        }
        // 链接：https://leetcode.cn/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode-solution/
        //TODO 展示放弃。。。
        public boolean isMatch(String s, String p) {
            if (p == null || p.length() == 0) return (s == null || s.length() == 0);

            int strLen = s.length();
            int pLen = p.length();

            boolean[][] f = new boolean[strLen + 1][pLen + 1];
            f[0][0] = true;//
            //前 i j个字符是否能够匹配。
            for (int i = 0; i <= strLen; ++i) {
                for (int j = 1; j <= pLen; ++j) {
                    if (p.charAt(j - 1) == '*') {
                        //当前是一个是 *
                        f[i][j] = f[i][j - 2];//匹配 无数次。  前i j-2个匹配。
                        if (matches(s, p, i, j - 1)) {
                            //前一个匹配
                            f[i][j] = f[i][j] || f[i - 1][j];
                        }
                    } else {
                        //当前
                        // chartIndex 匹配 && 之前字符串的也匹配
                        f[i][j] = matches(s, p, i, j) && f[i - 1][j - 1];
                    }
                }
            }
            return f[strLen][pLen];
        }

        //当前是不是匹配  i-1, j-1 的index
        public boolean matches(String s, String p, int i, int j) {
            if (i == 0) {
                return false;
            }
            if (p.charAt(j - 1) == '.') {//匹配所有
                return true;
            }
            return s.charAt(i - 1) == p.charAt(j - 1);//相等。
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}